package com.wp.基本算法.排序;

import java.util.Arrays;

/**
 * Created by 王萍 on 2017/8/23 0023.
 */
public class 快速排序 {

    public static void main(String[] args) {
        Comparable[] numbers = new Comparable[]{2, 3, 5, 1, 4, 9, 6};
        quickSort(numbers);
        Arrays.stream(numbers).forEach(number -> System.out.print(number + " "));

        Comparable[] chars = new Comparable[]{'w', 'a', 'n', 'g', 'p', 'i', 'n', 'g'};
        quickSort(chars);
        Arrays.stream(chars).forEach(number -> System.out.print(number + " "));
    }

    public static Comparable[] quickSort(Comparable[] array) {
        sort(array, 0, array.length - 1);
        return array;
    }

    //先以第一个数base为基础，使数组的元素满足小于base的在其左边，大于base的在其右边。
    //然后递归其左半部分，右半部分也满足这个规律，递归结束后，整个数组就是排好序的。
    public static Comparable[] sort(Comparable[] array, int start, int end) {
        if (start >= end) return null;
        Comparable base = array[start];
        Comparable tmp;
        //用两个指针，low向后移，当low所指的元素大于base时，high向后移，当high所指的元素小于base时，
        //交换这两个数的位置，直到low>=high。
        int low = start, high = end + 1;
        while (true) {
            while (array[++low].compareTo(base) < 0)
                if (low == end) break;
            while (array[--high].compareTo(base) > 0)
                if (high == start) break;
            if (low >= high) break;
            tmp = array[low];
            array[low] = array[high];
            array[high] = tmp;
        }
        tmp = array[high];
        array[high] = array[start];
        array[start] = tmp;
        sort(array, start, high - 1);
        sort(array, high + 1, end);
        return array;
    }
}
